import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.PriorityQueue;

class HNode implements Comparable<HNode> {
	HNode left;
	HNode right;
	HNode parent;
	char code = 0;
	int feq;
	StringBuffer sequence;

	public HNode(int feq) {
		super();
		this.feq = feq;
	}

	public StringBuffer getSequence() {
		if (sequence == null)
			sequence = new StringBuffer();
		return sequence;
	}

	public void setCode(char code) {
		this.code = code;
	}

	public char getCode() {
		return code;
	}

	public void setLeft(HNode node) {
		this.left = node;
		if (node != null)
			node.parent = this;
	}

	public void setRight(HNode node) {
		this.right = node;
		if (node != null) {
			node.parent = this;
		}
	}

	@Override
	public int compareTo(HNode o) {
		return this.feq - o.feq;
	}
}

public class HuffmanCode {
	public static void main(String[] args) throws IOException {
		PriorityQueue<HNode> queue = new PriorityQueue<HNode>();
		/*
		 * HNode h1 = new HNode(10); h1.setCode('A'); HNode h2 = new HNode(30);
		 * h2.setCode('B'); HNode h3 = new HNode(1); h3.setCode('C');
		 * queue.add(h1); queue.add(h2); queue.add(h3); while
		 * (!queue.isEmpty()){ System.out.print(queue.remove().code+" "); }
		 */

		InputStreamReader isr = new InputStreamReader(
				new FileInputStream("txt"), "GBK");
		HashMap<Character, Integer> chars = new HashMap<Character, Integer>();
		int c;
		while ((c = isr.read()) != -1) {
			Character ct = Character.valueOf((char) c);
			Integer counter = chars.get(ct);
			if (counter == null) {
				counter = 1;
			} else {
				counter += 1;
			}
			chars.put(ct, counter);
		}
		isr.close();
		for (Iterator<Character> citer = chars.keySet().iterator(); citer
				.hasNext();) {
			Character ct = citer.next();
			Integer cfeq = chars.get(ct);
			HNode hn = new HNode(cfeq);
			hn.setCode(ct);
			queue.add(hn);
		}
		while (queue.size() > 1) {
			HNode hn1 = queue.remove();
			HNode hn2 = queue.remove();
			HNode new_node = new HNode(hn1.feq + hn2.feq);
			new_node.left = hn1.feq < hn2.feq ? hn1 : hn2;
			new_node.right = hn1.feq > hn2.feq ? hn1 : hn2;
			hn1.parent = new_node;
			hn2.parent = new_node;
			queue.add(new_node);
		}
		HNode root_node = queue.remove();
		HashMap<Character, CharSequence> char_code_map = new HashMap<Character, CharSequence>();
		HashMap<CharSequence, Character> code_char_map = new HashMap<CharSequence, Character>();

		visit(root_node, char_code_map, code_char_map);
		for (Iterator<Character> citer = char_code_map.keySet().iterator(); citer
				.hasNext();) {
			Character cc = citer.next();
			CharSequence seq = char_code_map.get(cc);
			switch (cc) {
			case '\r':
				System.out.print("\\r");
				break;
			case '\t':
				System.out.print("\\t");
				break;
			case '\n':
				System.out.print("\\n");
				break;
			default:
				System.out.print(cc);
			}
			System.out.println(":" + seq);
		}
	}

	private static void visit(HNode node,
			HashMap<Character, CharSequence> char_code_map,
			HashMap<CharSequence, Character> code_char_map) {
		if (node.code > 0) { // leaf
			String string = node.getSequence().toString();
			char_code_map.put(node.code, string);
			code_char_map.put(string, node.code);
		} else {
			HNode left = node.left;
			if (left != null) {
				left.getSequence().append('0');
				visit(left, char_code_map, code_char_map);
			}
			HNode right = node.right;
			if (right != null) {
				right.getSequence().append('1');
				visit(right, char_code_map, code_char_map);
			}
		}
	}
}
